package zoran.wang.graph;

import java.util.LinkedList;
import java.util.List;

/**
 * DFS 深度优先搜索，包含了：
 * 1. 递归遍历图（邻接表）的所有节点
 * 2. 递归遍历图（邻接表）的所有边
 * 3. 递归遍历图（邻接矩阵）的所有节点
 * 4. 递归遍历图（邻接矩阵）的所有边
 *
 * @author wangzhuo
 * @time 2025-04-14-15:33
 */
public class RecursionTraversal {

    /**
     * DFS（邻接表） 定义：递归遍历所有节点
     * 当图不具有连通性时，会漏掉一些节点
     *
     * @param graph
     */
    public void traverseVertex(List<Integer>[] graph) {

        traverseVertex(graph, 0, new boolean[graph.length]);
    }

    /**
     * 从 vertex 开始遍历图的所有节点
     *
     * @param graph
     * @param vertex
     */
    public void traverseFromVertex(List<Integer>[] graph, int vertex) {
        traverseVertex(graph, vertex, new boolean[graph.length]);
    }

    // 使用 visited 防止节点重复遍历
    private void traverseVertex(List<Integer>[] graph, int vertex, boolean[] visited) {

        // base case
        if (vertex < 0 || vertex >= graph.length || visited[vertex]) return;

        System.out.print(vertex + " ");
        visited[vertex] = true;

        // 递归遍历节点 vertex 的相邻节点
        for (Integer neighbor : graph[vertex]) {
            traverseVertex(graph, neighbor, visited);
        }
    }

    /**
     * DFS（邻接表） 定义：遍历 src->des 经过的所有节点
     *
     * @param graph
     * @param src
     * @param destination
     */
    public void traverseEdge(List<Integer>[] graph, int src, int destination) {
        traverseEdge(graph, src, destination, new LinkedList<>(), new boolean[graph.length]);
    }

    // onPath 的作用是防止有双向边
    private void traverseEdge(List<Integer>[] graph, int src, int destination, LinkedList<Integer> path, boolean[] onPath) {

        // base case
        if (src < 0 || src >= graph.length || onPath[src]) return;

        // 前序位置
        path.add(src);
        onPath[src] = true;

        // 到达目标节点
        if (src == destination) {
            System.out.println(path);
        }

        // 递归遍历所有相邻节点
        for (Integer vertex : graph[src]) {
            traverseEdge(graph, vertex, destination, path, onPath);
        }

        // 后序位置
        path.removeLast();
        onPath[src] = false;
    }

    /**
     * DFS（邻接矩阵） 定义：递归遍历所有节点
     *
     * @param graph
     */
    public void traverseVertex(int[][] graph) {

        traverseVertex(graph, 0, new boolean[graph.length]);
    }

    private void traverseVertex(int[][] graph, int vertex, boolean[] visited) {

        // base case
        if (vertex < 0 || vertex >= graph.length || visited[vertex]) return;

        // 前序位置
        visited[vertex] = true;
        System.out.print(vertex + " ");

        // 遍历所有相邻节点
        for (int i = 0; i < graph[vertex].length; i++) {
            if (graph[vertex][i] != 0) {
                traverseVertex(graph, i, visited);
            }
        }

        // 后序位置，遍历节点不要 visited[vertex] = false ！！！！
    }

    /**
     * DFS（邻接矩阵） 定义：递归 0->n-1 的所有边
     *
     * @param graph
     */
    public void traverseEdge(int[][] graph) {

        traverseEdge(graph, 0, graph.length - 1, new LinkedList<>(), new boolean[graph.length]);
    }

    /**
     * 定义：遍历 vertex->dest 经过的所有节点
     *
     * @param graph
     * @param vertex
     */
    public void traverseEdge(int[][] graph, int vertex, int dest) {
        traverseEdge(graph, vertex, dest, new LinkedList<>(), new boolean[graph.length]);
    }

    // // onPath 防止双向边
    private void traverseEdge(int[][] graph, int vertex, int dest, LinkedList<Integer> path, boolean[] onPath) {

        // base case 注意邻接矩阵
        if (vertex < 0 || vertex > graph.length || onPath[vertex]) return;

        // 前序位置
        path.add(vertex);
        onPath[vertex] = true;

        // 到达目标节点
        if (vertex == dest) System.out.println(path);

        // 遍历相邻节点，v表示相邻节点，graph[vertex[v]表示权重
        for (int v = 0; v < graph[vertex].length; v++) {
            if (graph[vertex][v] != 0) traverseEdge(graph, v, dest, path, onPath);
        }

        // 后序位置
        path.removeLast();
        onPath[vertex] = false;
    }
}
